#include <iostream>
#include <fstream>
#include <limits>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;
using std::pair;

template <typename Key, typename Value>
class PriorityQueue {
public:
	PriorityQueue() {};
	~PriorityQueue() {};
	void changeKey(Key key, Value value);
	void push(Key key, Value value);
	Value pop();
	void deleteValue(Value value);
	bool containValue(Value value);
	bool empty();
	size_t size() { return mMap.size();}
private:
	map<Value, Key> mMap;
};

template <typename Key, typename Value>
void PriorityQueue<Key, Value>::push(Key key, Value value) {
	mMap[value]=key;
}

template <typename Key, typename Value>
Value PriorityQueue<Key, Value>::pop() {
	return (min_element(mMap.begin(), mMap.end()))->first;
}

template <typename Key, typename Value>
void PriorityQueue<Key, Value>::changeKey(Key key, Value value) {
	mMap[value]=key;
}

template <typename Key, typename Value>
bool PriorityQueue<Key, Value>::containValue(Value value) {
	return (mMap.find(value)!=mMap.end());
}

template <typename Key, typename Value>
void PriorityQueue<Key, Value>::deleteValue(Value value) {
	if (mMap.find(value)!=mMap.end()) {
		mMap.erase(value);
	}
}

template <typename Key, typename Value>
bool PriorityQueue<Key, Value>::empty() {
	return mMap.empty();
}
